NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c-part1/7821

Text File | 1996-08-05 | 2.8 KB | 83 lines

Path: sun001.spd.dsccc.com!spd!jmccarty
From: [e-mail] (Mike McCarty)
Newsgroups: comp.lang.c
Subject: Re: line intersection in C
Date: 29 Feb 1996 02:10:46 GMT
Organization: DSC Communications Corporation, Plano, Texas USA
Message-ID: <4h31v6$[e-mail]>
References: <[e-mail]> <[e-mail]>
NNTP-Posting-Host: aplo139.spd.dsccc.com

In article <[e-mail]>,
robert jacobs and jason jacobs  <[e-mail]> wrote:
)Daniel Castillo Molero wrote:
)>
)> Hello,
)>
)> I wonder if anybody can help me to find an algorithm in C to detect whether
)> two line segments intersect properly (I don't know if this is the correct
)> terminology, but by proper intersection I mean that the intersection is
)> not in the extreme of any of them and that one does not lie on top of
)> the other).
)> I need to test intersection just for line segments whose slope is a multiple
)> of 45 degrees, which I suppose may simplify the solution.
)>
)> I would greatly appreciate any sort of help.
)>
)> Daniel Castillo.
)>
)> [e-mail]
)>
)> --
)> * Daniel Castillo.  [e-mail] *
)
)Plug the end points of line segements into the equation for a line.
)Calculate the slope of the lines.  If the slopes are defferent the lines
)will intersect.
)
)Bob Jacobs


Bob, you really should have read the post before responding to it. They
guy is talking about line segments. This is not a simple problem.

Here's a try:

First, sort the endpoints of each of the two lines by x coordinates. If
the largest x for the first line is less than the smallest x for the
other, then there is no intersection (takes two checks). You can also
check the y's the same way.

Now, since the points are sorted by x's, you can check the slopes by
just seeing the direction of change. If the slopes are the same, then
no "proper" intersection is possible.

Now comes the hard part, I guess. I think that the best way may be to
use distances. Compute the equation of one of the lines. Find the
distances from the endpoints of the other line to the line you
computed. If one is negative, and the other is positive, you have a
real intersection. If they are of the same sign, then you have no
intersection. If one of the distances is zero, then you have a
degenerate T intersection.

If a line has equation

    Ax + By + C = 0

then the distance function of a given point (x,y) to the line is

    distance(x,y) = Ax + By + C

If the distance is 0, then the point is on the line, don't you see.

This is something I just came up with as fast as I could type. There may
be (probably is?) a better way.

Mike


----
char *p="char *p=%c%s%c;main(){printf(p,34,p,34);}";main(){printf(p,34,p,34);}

I don't speak for DSC.         <- They make me say that.